An electronic representation of a visual source image is typically generated by a device called a scanner. A scanner horizontally and vertically scans the image with an optical detector to produce a detector output signal. The detector output signal consists of a series of samples, wherein the magnitude of each sample corresponds to the light intensity of a particular element, or pixel, in the source image. The detector output signal samples are thus often referred to as pixel values.
The pixel values are then typically digitized and read by a computer. The computer organizes them into a two-dimensional array, called a bitmap, wherein the (x,y) coordinates of the array location into which a particular pixel value is written are determined by the spatial position of the corresponding elemental area of the image. Each pixel value in the bitmap is a representation of the intensity, or some colorimetric property of a corresponding pixel in the source image.
Image processing operations such as translation, rotation, scaling, and coloring can then be performed on the bitmap representation, to generate an altered image. The altered image can then be further processed, or presented to a graphic display, printer, typesetter, or some other image output device.
However, the scanning process sometimes does not result in a bitmap that is a perfect representation of the source image. For example, if the source image originates as a line art sketch drawn by a human with a pen and paper, small gaps may be formed wherever thin lines in the original sketch do not align with the scan path of the optical detector.
In other words, if a horizontal thin line is sketched at an angle other than exactly straight across the paper, at some point during the scanning process the sketched line will cross from one horizontal scan line to an adjacent horizontal scan line. At such a point the pixel values representing the sketched line lie partially in one horizontal row and partially in an adjacent horizontal row of the bitmap.
Thus, when the optical detector is scanned over the image, some of the light energy from the thin sketched line, say 55%, is when the first horizontal line of pixels is scanned, and the remaining 45% of the energy is detected when the adjacent line of pixels is scanned. In the case of a black and white scanner, the optical detector typically uses a threshold detection scheme wherein a pixel is called white if, say, 50% or more of the light energy of a solid white pixel is present at a particular position of the scanner. As a result, neither scan of the image will result in the correct detection of the corresponding pixels as black. An erroneous white pixel "gap" in the bitmap representation of the sketched line thus results.
The response of a scanner to thin lines can be determined and is analogous to the response of a bandlimited detector to a modulated signal in a communications system. This response is often referred to as the scanner's modulation transfer function (MTF).
When the pen is lifted and returned to the surface of the paper, similar gaps may also be created.
Regardless of their sources, such gaps are usually so small that they are difficult to detect visually, and thus they do not appreciably affect the quality of the output image.
However, the presence of gaps in lines may adversely affect certain image processing operations. For example, an area fill algorithm typically operates by setting the value of all pixels within a bounded area to a particular background color. The bounded area is usually defined by lines of pixels of a certain foreground color. If gaps exists between the pixels that define the lines, then the area fill algorithm will "leak" outside the desired area, since that area is not actually bounded.
While a human may visually examine the image and fill in the gaps before an area fill operation is initiated, this is not practical in most instances. Consider that even if the source image is fairly small, say three by five inches, and if the scanner operates at a resolution of 300 pixels per inch, the resulting bitmap will contain over 1.35 million pixels. This clearly is too many pixels for a human to examine individually.
Some have proposed techniques that eliminate features of an image which are smaller than a certain size without geometrically distorting other features. For example, see the successive dilation and erosion process described in Haralick, R. M., Sterberg, S. R. and Zhuang, X., "Image Analysis Using a Mathematical Morphology," IEEE Transactions on Pattern is and Machine Intelligence, Vol. PAMI-9 No. 4, July, 1987, pp. 532-550. The dilation process sums a small fixed array of values to each pixel in a neighborhood surrounding a current pixel via matrix addition -- the result is to "smear" the image, thereby "expanding" each small image feature so that it will merge with adjacent features. A subsequent erosion, or subtraction of the fixed array, "refocuses" or "shrinks" the image features back to their original size, in such a manner as to retain connections between any features merged during the dilation process. Unfortunately, this technique will indiscriminately bridge pixel areas which do not originate from the scanning process, and which are intended to remain separated.
What is needed is a technique for automatically detecting and bridging gaps created by the scanning process, without indiscriminately bridging gaps intentionally formed in the source image. This would prevent a subsequently executed area fill algorithm from leaking outside its intended boundaries.
The technique should also avoid bridging areas which are not actual line gaps, such as a gap intentionally formed between a line and the side of an object.
Because images may be stored in a variety of formats, including a raster format, wherein a value is specified for each pixel, as well as a run encoded format, wherein the starting coordinates or lengths of runs of pixels are specified, the technique should be easy to adapt to as many image encoding formats as possible.